package 栈和队列;

/**
 * ---------------------------------------------------------
 * <h></h>
 * <p></p>
 * Created by Frank on 2021/4/2.
 * <a href="mailto:frankyao10110@gmail.com">Contact me</a>
 * ---------------------------------------------------------
 */
public class _接雨水 {
    public static void main(String[] args) {
        int[] height = new int[]{2,0,2};
        int sum = trap(height);
        System.out.println("sum: " + sum);
    }

    public static int trap(int[] height) {
        if (height == null || height.length == 0) return 0;
        int midInx = findHighest(height, 0, height.length);
        int lMaxInx = findHighest(height, 0, midInx);
        int rMaxInx = findHighest(height, midInx + 1, height.length);

        int lTrap = 0;
        int rTrap = 0;

        if (lMaxInx != midInx) {
            lTrap = height[lMaxInx] * (midInx - lMaxInx - 1) - sumOfHeight(height, lMaxInx, midInx);
        }
        if (rMaxInx != midInx) {
            rTrap = height[rMaxInx] * (rMaxInx - midInx - 1) - sumOfHeight(height, midInx, rMaxInx);
        }

        while (lMaxInx > 0) {
            int oldInx = lMaxInx;
            lMaxInx = findHighest(height, 0, lMaxInx);
            lTrap += trapLeftSum(height, lMaxInx, oldInx);
        }

        while (rMaxInx < height.length - 1) {
            int oldInx = rMaxInx;
            rMaxInx = findHighest(height, rMaxInx + 1, height.length);
            rTrap += trapRightSum(height, oldInx, rMaxInx);
        }

        return lTrap + rTrap;
    }

    private static int trapLeftSum(int[] height, int l, int r) {
        int trap = height[l] * (r - l - 1) - sumOfHeight(height, l, r);

        if (trap < 0) return 0;

        return height[l] * (r - l - 1) - sumOfHeight(height, l, r);
    }

    private static int trapRightSum(int[] height, int l, int r) {
        int trap = height[r] * (r - l - 1) - sumOfHeight(height, l, r);

        if (trap < 0) return 0;

        return height[r] * (r - l - 1) - sumOfHeight(height, l, r);
    }

    /**
     * 找到范围内最大的值的下标
     * @param height 查找数组
     * @param l 起点
     * @param r 终点
     * @return 目标值下标
     */
    private static int findHighest(int[] height, int l, int r) {
        int maxIdx = l;
        if (l == r) {
            if (r == 0) {
                return 0;
            }else {
                return height.length - 1;
            }
        }

        for (int i = l; i < r; i++) {
            if (height[i] > height[maxIdx]) {
                maxIdx = i;
            }
        }

        return maxIdx;
    }

    private static int sumOfHeight(int[] height, int l, int r) {
        int sum = 0;
        for (int i = l + 1; i < r; i++) {
            sum += height[i];
        }

        return sum;
    }
}
